package first.niuke.midding;

/**
 * @ClassName NC53
 * @description:
 * @author: 荣燊
 * @create: 2021-06-22 09:58
 **/
public class NC53 {


    // 删除链表的倒数第n个节点（从1开始）

    /**
     * 思路：双指针，中间差n-1个，当第二个到了链表尾部，第一个就在倒数第n个
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        if (head == null) {
            return head;
        }

        ListNode node1 = head;
        ListNode node2 = head;
        ListNode pre = null;

        while (n > 0) {
            if (node2 != null) {
                node2 = node2.next;
            } else {
                return null;
            }
            n--;
        }

        // 链表长度等于n的情况，此时node2==null，要删除第一个节点
        if (node2 == null) {
            return head.next;
        }

        while (node2 != null) {
            node2 = node2.next;
            pre = node1;
            node1 = node1.next;
            // 如果此时node2==null
            if (node2 == null) {
                pre.next = node1.next;
            }
        }

        return head;
    }

    public class ListNode {
       int val;
       ListNode next = null;
    }
}
